package 纯数组;

import java.util.Arrays;

public class JZ53在排序数组中查找数字I {

    /**
     * 统计一个数字在排序数组中出现的次数。
     *
     * 示例 1:
     * 输入: nums = [5,7,7,8,8,10], target = 8
     * 输出: 2
     * 示例 2:
     * 输入: nums = [5,7,7,8,8,10], target = 6
     * 输出: 0 
     *
     * 限制：
     * 0 <= 数组长度 <= 50000
     *
     * 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
     */

    public int search(int[] nums, int target) {

        int index=binarySearch(nums,0,nums.length-1,target);
        if(index==-1){
            return 0;
        }
        int count=1;
        for (int i = index+1; i < nums.length&&nums[i]==target; i++) {
            count++;
        }
        for (int i = index-1; i >= 0&&nums[i]==target; i--) {
            count++;
        }
        return count;
    }

    private int binarySearch(int[] arr,int left,int right,int target) {

        int mid;
        while (left<=right){
            mid=(right-left)/2+left;
            int num=arr[mid];

            if(num==target){
                return mid;
            }
            if(num<target){
                //目标在右边
                left=mid+1;
            }else{
                right=mid-1;
            }

        }

        return -1;
    }

}